
// 时间复杂度 O(n^2)
// 空间复杂度 O(1)

const { LinkedList, ListNode } = require('../1. 链表基础/1. 建立线性链表')

function insertionSort(head) {
    if (!head || !head.next) {
        return head
    }
    let dummyHead = new ListNode(-1, head)
    let sortedList = head
    let cur = head.next

    while (cur) {
        if (sortedList.val <= cur.val) {
            sortedList = sortedList.next
        } else {
            let prev = dummyHead
            while (prev.next.val <= cur.val) {
                prev = prev.next
            }
            sortedList.next = cur.next
            cur.next = prev.next
            prev.next = cur
        }
        cur = sortedList.next
    }
    return dummyHead.next
}

const linkList = new LinkedList([2, 5, 1, 6, 3, 4])
insertionSort(linkList.head)
console.log(linkList)